package com.shm.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 423. 从英文中重建数字
 * 给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "owoztneoer"
 * 输出："012"
 * 示例 2：
 *
 * 输入：s = "fviefuro"
 * 输出："45"
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 105
 * s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一
 * s 保证是一个符合题目要求的字符串
 * @author SHM
 */
public class OriginalDigits {

    /**
     * 模拟
     * 题目要求我们将打乱的英文单词重建为数字。
     *
     * 我们可以先对 s 进行词频统计，然后根据「英文单词中的字符唯一性」确定构建的顺序，最后再对答案进行排序即可。
     *
     * 具体的，zero 中的 z 在其余所有单词中都没出现过，我们可以先统计 zero 的出现次数，并构建 00；然后观察剩余数字，其中 eight 中的 g 具有唯一性，构建 88；再发现 six 中的 x 具有唯一性，构建 66；发现 three 中的 h 具有唯一性（利用在此之前 eight 已经被删除干净，词频中仅存在 three 对应的 h)，构建 33 ...
     *
     * 最终可以确定一个可行的构建序列为 0, 8, 6, 3, 2, 7, 5, 9, 4, 1。
     * 时间复杂度：令 mm 为最终答案的长度，LL 为所有英文单词的字符总长度。构建答案的复杂度为 O(L + m)O(L+m)；对构建答案进行排序复杂度为 O(m\log{m})O(mlogm)。整体复杂度为 O(m\log{m})O(mlogm)
     * 空间复杂度：O(L + m)O(L+m)
     *
     *
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/solution/gong-shui-san-xie-nao-jin-ji-zhuan-wan-m-vg7a/
     * @param s
     * @return
     */
    public String originalDigits(String s) {
        String[] countWord = {"zero","one","two","three","four","five","six","seven","eight","nine"};
        int[] priority = {0,8,6,3,2,7,5,9,4,1};
        int n = s.length();
        int[] cntS = new int[26];
        for (int i = 0; i < n; i++) {
            cntS[s.charAt(i)-'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i : priority) {
            int k = Integer.MAX_VALUE;
            char[] charArray = countWord[i].toCharArray();
            for (char c : charArray) {
                k=Math.min(k,cntS[c-'a']);
            }
            for (char c : charArray) {
                cntS[c-'a']-=k;
            }
            while (k-->0){
                sb.append(i);
            }
        }
        char[] chars = sb.toString().toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }

    /**
     * 方法一：依次确定每一个数字的次数
     * 思路与算法
     *
     * 首先我们可以统计每个字母分别在哪些数字中出现：
     *
     * 字母	数字
     * e	0 1 3 5 7 8 9
     * f	4 5
     * g	8
     * h	3 8
     * i	5 6 8 9
     * n	1 7 9
     * o	0 1 2 4
     * r	0 3 4
     * s	6 7
     * t	2 3 8
     * u	4
     * v	5 7
     * w	2
     * x	6
     * z	0
     * 可以发现，\text{z, w, u, x, g}z, w, u, x, g 都只在一个数字中，即 0, 2, 4, 6, 80,2,4,6,8 中出现。因此我们可以使用一个哈希表统计每个字母出现的次数，那么 \text{z, w, u, x, g}z, w, u, x, g 出现的次数，即分别为 0, 2, 4, 6, 80,2,4,6,8 出现的次数。
     *
     * 随后我们可以注意那些只在两个数字中出现的字符：
     *
     * \text{h}h 只在 3, 83,8 中出现。由于我们已经知道了 88 出现的次数，因此可以计算出 33 出现的次数。
     *
     * \text{f}f 只在 4, 54,5 中出现。由于我们已经知道了 44 出现的次数，因此可以计算出 55 出现的次数。
     *
     * \text{s}s 只在 6, 76,7 中出现。由于我们已经知道了 66 出现的次数，因此可以计算出 77 出现的次数。
     *
     * 此时，我们还剩下 11 和 99 的出现次数没有求出：
     *
     * \text{o}o 只在 0, 1, 2, 40,1,2,4 中出现，由于我们已经知道了 0, 2, 40,2,4 出现的次数，因此可以计算出 11 出现的次数。
     * 最后的 99 就可以通过 \text{n, i, e}n, i, e 中的任一字符计算得到了。这里推荐使用 \text{i}i 进行计算，因为 \text{n}n 在 99 中出现了 22 次，\text{e}e 在 33 中出现了 22 次，容易在计算中遗漏。
     *
     * 当我们统计完每个数字出现的次数后，我们按照升序将它们进行拼接即可。
     * 复杂度分析
     *
     * 时间复杂度：O(|s|)O(∣s∣)，其中 |s|∣s∣ 是字符串 ss 的长度。
     *
     * 空间复杂度：O(|\Sigma|)O(∣Σ∣)，其中 \SigmaΣ 表示字符集，|\Sigma|∣Σ∣ 表示字符集的大小，在本题中 \SigmaΣ 为所有在 0 \sim 90∼9 中出现的英文字母。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/solution/cong-ying-wen-zhong-zhong-jian-shu-zi-by-9g1r/
     * @param s
     * @return
     */
    public String originalDigits_1(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map.put(c,map.getOrDefault(c,0)+1);
        }
        int[] cnt = new int[10];
        cnt[0] = map.getOrDefault('z',0);
        cnt[2] = map.getOrDefault('w',0);
        cnt[4] = map.getOrDefault('u',0);
        cnt[6] = map.getOrDefault('x',0);
        cnt[8] = map.getOrDefault('g',0);

        cnt[3] = map.getOrDefault('h',0)-cnt[8];
        cnt[5] = map.getOrDefault('f',0)-cnt[4];
        cnt[7] = map.getOrDefault('s',0)-cnt[6];

        cnt[1] = map.getOrDefault('o',0)-cnt[0]-cnt[2]-cnt[4];

        cnt[9] = map.getOrDefault('i',0)-cnt[5]-cnt[6]-cnt[8];

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                sb.append(i);
            }
        }
        return sb.toString();
    }
}
